Brakedown and Shockwave

(updated )

$$ \gdef\setn#1{\mathcal{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\enc{\mathsf{enc}} \gdef\p#1{\left({#1}\right)} $$

From GLS⁺21. Like in Hyrax, we will create a commitment to a matrix $\mat M ∈ 𝔽^{n×m}$ such that we can later compute double contractions $$ s = \vec p ⋅ \mat M ⋅ \vec q = \sum_{ij} \mat M_{ij}⋅p_i⋅q_j $$ for some arbitrary vectors $\vec p, \vec q$.

Take a linear code $\enc: 𝔽^m→𝔽^M$ with rate $ρ = m/M$. When instantiated with a linear-time encoding codes, it is known as Brakedown Polynomial Commitments. When instantiated with Reed-Solomon codes, it is known as Ligero Polynomial Commitments AHIV17. (And when used to instantiate Spartan they are known as Brakedown and Shockwave respectively.)

Commitment

Prover has $\mat M ∈ 𝔽^{n×m}$.

  1. Prover sends the column-wise Merkle-hash of $\mat E = [\enc(\mat M_i)]_{i∈[n]}$.

Evaluation

In addtion to above, prover and verifier have $\vec p ∈ 𝔽^n$, $\vec q ∈ 𝔽^m$ and want to compute the double contraction $s = \vec p ⋅ \mat M ⋅ \vec q$. The protocol is as above, with $\vec r$ substituted by $\vec p$:

  1. Verifier sends random $\mat R ∈ 𝔽^{k×n}$.
  2. Prover sends $\mat U = [\vec p; \mat R]⋅ \mat M$.
  3. Verfier computes $\mat C = [\enc(\mat U_i)]_{i∈[k]}$.
  4. Verifier sends $\setn C ⊂ [m]$.
  5. Prover decommits columns $\mat E_{\setn C}$.
  6. Verifier checks $\mat C_{\setn C} = [\vec p; \mat R] ⋅ \mat E_{\setn C}$.
  7. Verifier checks $s = \mat U_0 ⋅ \vec q$

Parameter Choices for Reed-Solomon Codes

Given security target $λ$ in bits. Assuming the matrix dimensions and encoding rate are fixed, the main protocol parameters are the number of random combinations $k$ and queries $|\setn C|$. Following GLS⁺21 theorem B.7 (see also reference implementation 1 2), these are set to:

$$ \begin{aligned} k = 1 + \left\lfloor \frac{λ - 1}{\log_2 |𝔽| - \log_2 M} \right\rfloor && |\setn C| = \left\lceil \frac{λ}{1 - \log_2 (1 + \frac{m}{M})} \right\rceil \end{aligned} $$

For $λ = 128$ and large field $|𝔽| ≥ 2^{200}$ with reasonably sized $M < 2^{64}$ we will always have $k = 1$. The number of queries $|\setn C|$ decays exponentially from about $2.5 ⋅ λ$ for $M = 2⋅m$ down to $λ$ as $M$ increases.

The randomized checks created by $k$ serve to verify that the commitment is constructed correctly. This only has to be done once, so for repeated evaluations or when the commitment is trusted we can set $k=0$ (see GLS⁺21 p. 12).

Question. Does the process of grinding as used in FRI help to boost soundness and reduce $|\setn C|$?

References

Remco Bloemen
Math & Engineering
https://2π.com